package LeetcodeTest_sixteen;

import org.omg.CORBA.MARSHAL;

import java.util.ArrayList;
import java.util.Arrays;

//黄金矿工
public class getMaximumGold
{
    public static void main(String[] args)
    {
        int num[][]={{1,0,7},{2,0,6},{3,4,5},{0,3,0},{9,0,20}};
        boolean a[]=new boolean[1];
        System.out.println(solution.getMaximumGold(num));
    }
}
class solution
{
    public static int getMaximumGold(int[][] grid)
    {
        int i,j;
        int result,maxResult;
        result=maxResult=0;
        for (i=0;i<grid.length;i++)
        {
            for (j=0;j<grid[i].length;j++)
            {
                if(grid[i][j]!=0)
                {
                    result=backtrace(grid,i,j);
                    if(result>maxResult)
                        maxResult=result;
                }
            }
        }
        return maxResult;
    }
    public static int backtrace(int[][] grid, int i, int j)
    {
        int answer = 0;
        int temp=grid[i][j];
        grid[i][j]=0;
        if (i-1>=0 && grid[i-1][j]!=0)
            answer = Math.max(backtrace(grid, i - 1, j), answer);
        if (i+1<grid.length && grid[i+1][j]!=0)
            answer = Math.max(backtrace(grid, i + 1, j), answer);
        if (j-1>=0 && grid[i][j-1]!=0)
            answer = Math.max(backtrace(grid, i, j - 1), answer);
        if (j+1<grid[i].length && grid[i][j+1]!=0)
            answer = Math.max(backtrace(grid, i, j + 1), answer);
        grid[i][j]=temp;
        return answer + grid[i][j];
    }
}